package LeetCode._02算法基础.day20其他;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author 挚爱之夕
 * @version 困难
 * @implSpec 给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。
 * 求最多有多少个点在同一条直线上。
 *
 * 输入：points = [[1,1],[2,2],[3,3]]
 * 输出：3
 * @since 2022 - 09 - 16 - 16:35
 */
public class _149直线上最多的点数 {
    public static void main(String[] args) {
        /*
        [[0,0],[4,5],[7,8],[8,9],[5,6],[3,4],[1,1]]
         */
//        int[][] points = {
//                {1,1},
//                {3,2},
//                {5,3},
//                {4,1},
//                {2,3},
//                {1,4}
//        };

        int[][] points = {
                {0, 0},
                {4, 5},
                {7, 8},
                {8, 9},
                {5, 6},
                {3, 4},
                {1, 1}
        };
        System.out.println(new _149直线上最多的点数().maxPoints(points));
    }
    //by me , 考虑两点构成直线的情况： 水平 、 竖直 、 倾斜
    //注意 k 和 b 不能取整数

    Map<Double, Map<Double, Set<int[]>>> map = new HashMap<>();// Map<k, Map<b, points>>
    public int maxPoints(int[][] points) {
        if(points.length == 1)
            return 1;
        int res = 0, len = points.length;
        double k, b;
        int[] point1, point2;
        for(int i = 0; i < len; i++){
            point1 = points[i];
            for(int j = i + 1; j < len; j++){
                point2 = points[j];
                if(point1[0] == point2[0]){ //垂直
                    k = Integer.MAX_VALUE;
                    b = getParam2(2, point1, point2);
                }else if(point1[1] == point2[1]){   //水平
                    k = 0;
                    b = getParam2(1, point1, point2);
                }else{  //倾斜
                    k = (point1[1] - point2[1]) * 1.0 / (point1[0] - point2[0]);
                    b = getParam2(0, point1, point2);
                }
                //k, b 都相同的在一条直线上
                if(map.containsKey(k)){
                    Map<Double, Set<int[]>> map2 = map.get(k);
                    if(map2.containsKey(b)){
                        map2.get(b).add(point1);
                        map2.get(b).add(point2);
                    }else{
                        Set<int[]> set = new HashSet<>();
                        set.add(point1);
                        set.add(point2);
                        map2.put(b, set);
                    }
                }else{
                    Map<Double, Set<int[]>> map2 = new HashMap<>();
                    Set<int[]> set = new HashSet<>();
                    set.add(point1);
                    set.add(point2);
                    map2.put(b, set);
                    map.put(k, map2);
                }
                res = Math.max(res, map.get(k).get(b).size());
            }
        }
        //    Map<Integer, Map<Integer, Set<Integer>>> map = new HashMap<>();
        for(double kk : map.keySet()){
            Map<Double, Set<int[]>> map22 = map.get(kk);
            for(double bb : map22.keySet()){
                System.out.println("k :" + kk +" b:" + bb);
                for(int[] pp : map22.get(bb)){
                    System.out.print("(" +pp[0] +", " + pp[1] +") " + " ");
                }
                System.out.println("\n----------------");
            }
        }
        return res;
    }

    /**
     * 获取b值
     * @param kind 直线种类
     * @param point1 点1
     * @param point2 点2
     * @return b值
     */
    public double getParam2(int kind, int[] point1, int[] point2){
        if(kind == 1){  //水平
            return point1[1];   //与y轴 交点的y值
        }else if(kind == 2){    //垂直
            return point1[0];   //与x轴 交点的x值
        }else{
            double k = (point1[1] - point2[1]) * 1.0 / (point1[0] - point2[0]);
            return point1[1] - k * point1[0]; // y = kx + b 中的b值
        }
    }

    /*官方思路*/
    public int maxPoints1(int[][] points) {
        int n = points.length;
        if (n <= 2) {
            return n;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (res >= n - i || res > n / 2) {  //找不到更大的了
                break;
            }
            //第 i 个点 和其后的所有点比较
            Map<Integer, Integer> map = new HashMap<>();
            for (int j = i + 1; j < n; j++) {
                //表示斜率
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                if (x == 0) {
                    y = 1;
                } else if (y == 0) {
                    x = 1;
                } else {
                    if (y < 0) {
                        x = -x;
                        y = -y;
                    }
                    int gcdXY = gcd(Math.abs(x), Math.abs(y));
                    x /= gcdXY;
                    y /= gcdXY;
                }
                int key = y + x * 20001;
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
            int maxn = 0;
            for (Map.Entry<Integer, Integer> entry: map.entrySet()) {
                int num = entry.getValue();
                maxn = Math.max(maxn, num + 1); // 第i个点也要算
            }
            res = Math.max(res, maxn);
        }
        return res;
    }

    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}
